/*
    最大子序和
    给定一个数组nums，找到一个具有最大和的连续子数组（子数组最少含有1个元素）
    返回其最大和
*/


#include <stdio.h>
#include <math.h>

//方法1、贪心算法
int maxSubArray(int* nums, int numsSize)
{
    if(nums == NULL) return 0; //错误情况

    int pre = 0, maxAns = nums[0];

    for(int i=0; i<numsSize; i++)
    {
        pre = fmax(pre+nums[i],nums[i]);
        maxAns = fmax(maxAns,pre);
    }
    return maxAns;
}

int main(int argc, char const *argv[])
{
    int nums[] = {-2,1,-3,4,-1,2,1,-5,4};
    int numsSize = sizeof(nums)/sizeof(int);
    
    printf("%d\n",maxSubArray(nums,numsSize));
    return 0;
}


